package com.javabase.y2022.m05.day0517.v3;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/17 上午 10:14
 * @version: 1.0
 */
public class Solution {
    public void mergeSorted(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        process(arr, L, R);
    }

    public int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        int ans = process(arr, L, M)
                + process(arr, M + 1, R)
                + merge(arr, L, M, R);
        return ans;
    }

    public int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int p1 = 0, p2 = M + 1;
        int i = 0;
        int ans = 0;
        while (p1 <= M && p2 <= R) {
            if (arr[p1] < arr[p2]) {
                ans += arr[p2] * (p2 - M + 1);
            }
            arr[i++] = arr[p1] < arr[p2] ? arr[p1] : arr[p2];
        }
        while (p1 <= M) {
            arr[i++] = arr[p1++];
        }
        while (p2 <= R) {
            arr[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
        return ans;
    }

    public void mergeSorted2(int[] arr) {
        int N = arr.length;
        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;
            while (L < N) {
                if (L + mergeSize >= N) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = M + Math.min(mergeSize, N - M - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            if (mergeSize * 2 > N) {
                break;
            }
            mergeSize <<= 1;
        }
    }
}
